package com.example.myletcodelearing.one.find


/**
 * https://offer.hi-dhl.com/#/algorithm/03-number
 * @author tgw
 * @date 2022/11/7
在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，
输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

示例:

现有矩阵 matrix 如下：

[
[1,   4,  7, 11, 15],
[2,   5,  8, 12, 19],
[3,   6,  9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30]
]
复制Error复制成功
给定 target = 5，返回 true。
给定 target = 20，返回 false。
 */

fun main(args: Array<String>) {
    var nums = arrayOf(3, 5, 7, 9, 6, 2, 1, 3)
    println("最小值：${-1 ushr 5}") //ushr对等java的 右移无符号（>>>） 位运算参考：https://www.jianshu.com/p/3ed61c2feac4

    val solution9 = Solution10.Solution().minArray(nums)
    val solution10 = Solution10.Solution().minArray2(nums)

    println("最小值：$solution9")
    println("最小值：$solution10")

}

private class Solution10 {
    class Solution {
        fun minArray(numbers: Array<Int>): Int {
            var left = 0
            var right = numbers.size - 1
            while (left < right) {
                val mid = (left + right) ushr 1
                when {
                    numbers[mid] > numbers[right] -> left = mid + 1
                    numbers[mid] < numbers[right] -> right = mid
                    else -> right = right - 1
                }
            }
            return numbers[left]
        }

        fun minArray2(numbers:  Array<Int>): Int {
            var l = 0
            var r = numbers.size - 1
            while (l < r) {
                val mid = (r - l shr 1) + l
                //只要右边比中间大，那右边一定是有序数组
                if (numbers[r] > numbers[mid]) {
                    r = mid
                } else if (numbers[r] < numbers[mid]) {
                    l = mid + 1
                    //去重
                } else r--
            }
            return numbers[l]
        }
    }

}
